#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <gmp.h>
#include <gsl/gsl_combination.h>


// gsl_combination * gsl_combination_alloc (size_t N, size_t K)
// void gsl_combination_init_first (gsl_combination * C)
// size_t gsl_combination_get (const gsl_combination * C, const size_t I)

// void mpz_setbit (mpz_t ROP, unsigned long int BIT_INDEX)
// int mpz_tstbit (mpz_t OP, unsigned long int BIT_INDEX)

typedef struct 
{
	int N; 
	int K;
	int szT;
	int ocup;
} sistema;

int comb(mpz_t* vetor, sistema s);
int CalcNumEletSitio(mpz_t integ, int n);
int CalcSzTotal(mpz_t integ, int n);

int main(void)
{
	int k, num;
	mpz_t* vetor;
	sistema s;
	
	int tam = 1000;
	
	s.N = 8;
	s.K = 4;
	s.szT = 0;
	s.ocup = 1;
	
	vetor = (mpz_t*)malloc(tam*sizeof(mpz_t));
	
	num = comb(vetor, s);
	
	for ( k = 0 ; k < num ; k++ )
	{
		gmp_printf("%Zd\n", vetor[k]);
	}
	
	printf("num = %d\n", num);
	
	
	return 0;
}

int comb(mpz_t* vetor, sistema s)
{
	gsl_combination* c;
	int i, j;
	int k = 0;
	int num;
	mpz_t integ;
	
	mpz_init(integ);
	c = gsl_combination_alloc(s.N, s.K);
	gsl_combination_init_first(c); // the first combination {0, 1, 2, K-1}
	
	do
	{
		mpz_set_ui (integ, 0);
		for ( i = 0 ; i < s.K ; i++ )
		{
			j = gsl_combination_get (c, i);
			mpz_setbit (integ, j);
		}
		num = CalcSzTotal(integ, s.N/2);
		if ( num == s.szT )
		{
			num = CalcNumEletSitio(integ, s.N/2);
			if ( num == s.ocup )
			{
				mpz_set(vetor[k], integ);
				k++;
			}
		}
	} while (gsl_combination_next(c) == GSL_SUCCESS);
	gsl_combination_free (c);
	return k;
}


int CalcSzTotal(mpz_t integ, int n)
{
	int i;
	int szt = 0;
	
	for ( i = 0 ; i < n ; i++ )
	{
		if ( mpz_tstbit(integ, 2*i) == 1 )
			szt--;
		if ( mpz_tstbit(integ, 2*i+1) == 1 )
			szt++;
	}
	return szt;
}
	
int CalcNumEletSitio(mpz_t integ, int n)
{
	int i;
	
	for ( i = 0 ; i < n ; i++ )
	{
		if ( (mpz_tstbit(integ, 2*i) == 1)  && (mpz_tstbit(integ, 2*i+1) == 1) )
		{
			return 0;
		}
	}
	return 1;
}

// gcc -lm -O3 -Wall -lgsl -lgslcblas -lgmp combinatorial.c -o combinatorial.exe